DROPS

Document

Short Paper

DOI: 10.4230/OASIcs.ATMOS.2021.17

Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper)

Authors: Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer

Published in: OASIcs, Volume 96, 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)

Abstract

In order to plan and schedule a demand-responsive public transportation system, both temporal and spatial changes in demand should be taken into account even at the line planning stage. We study the multi-period line planning problem with integrated decisions regarding dynamic allocation of vehicles among the lines. Given the NP-hard nature of the line planning problem, the multi-period version is clearly difficult to solve for large public transit networks even with advanced solvers. It becomes necessary to develop algorithms that are capable of solving even the very-large instances in reasonable time. For instances which belong to real public transit networks, we present results of a heuristic local branching algorithm and an exact approach based on constraint propagation.

Cite as

Güvenç Şahin, Amin Ahmadi Digehsara, and Ralf Borndörfer. Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper). In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 17:1-17:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17,
  author =	{\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf},
  title =	{{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17},
  URN =		{urn:nbn:de:0030-drops-148863},
  doi =		{10.4230/OASIcs.ATMOS.2021.17},
  annote =	{Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation}
}

@InProceedings{sahin_et_al:OASIcs.ATMOS.2021.17,
  author =	{\c{S}ahin, G\"{u}ven\c{c} and Ahmadi Digehsara, Amin and Bornd\"{o}rfer, Ralf},
  title =	{{Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation}},
  booktitle =	{21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021)},
  pages =	{17:1--17:6},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-213-6},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{96},
  editor =	{M\"{u}ller-Hannemann, Matthias and Perea, Federico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2021.17},
  URN =		{urn:nbn:de:0030-drops-148863},
  doi =		{10.4230/OASIcs.ATMOS.2021.17},
  annote =	{Keywords: public transportation, line planning, multi-period planning, local branching, constraint propagation}
}

Search Results

Documents authored by Ahmadi Digehsara, Amin

Efficient Algorithms for the Multi-Period Line Planning Problem in Public Transportation (Short Paper)

Abstract

Cite as

Thanks for your feedback!

Could not send message